//汉密尔顿回路
//hamilton_loop.cpp

//判断无向图中是否存在汉密尔顿回路，若存在则求出回路

//1)基础概念
//汉密尔顿路：
//图中存在一路经，通过图中每个节点恰好一次(可以经过边多次或不经过)
//汉密尔顿回路：
//图中存在一回路，通过图中每个节点恰好一次(可以经过边多次或不经过)
//汉密尔顿图：
//具有汉密尔顿回路的图
//完全图必为汉密尔顿图
//“半”汉密尔顿图：
//具有汉密尔顿路径但没有汉密尔顿回路的图
//至今尚未找到汉密尔顿图的非平凡充要条件
//
//2)判断存在汉密尔顿路的定理：
//无向汉密尔顿图的必要条件：已知汉密尔顿图 => 图的性质
//设无向图G=<V,E>是汉密尔顿图，则有：
//p(G-V1) <= |V1|，其中V1是节点集V的任意非空子集
//p(G-V1)是从G中删去V1(删除V1节点及关联的边)后所得图的连通分支的数量
//
//无向“半”汉密尔顿图的必要条件：
//设无向图G=<V,E>是无向“半”汉密尔顿图，则有：
//p(G-V1) <= |V1|+1
//
//无向“半”汉密尔顿图的充分条件：图的性质 => 是汉密尔顿图
//设图G=<V,E>是简单无向图
//若对于任意两个不相邻的节点u和v均有：
//degree(u)+degree(v) >= |V|-1，其中degree是节点度数，|V|为图G的节点数量
//则图G是“半”汉密尔顿图
//
//无向汉密尔顿图的充分条件：
//设图G=<V,E>是简单无向图
//若对于任意两个不相邻的节点u和v均有：
//degree(u)+degree(v) >= |V|，则图G存在汉密尔顿回路
//
//3)极大路径和图的闭包
//极大路径：
//图中的路径L，如果L的起点和终点都不与L外的节点相邻
//则称L是一条极大路径，即L再无法向外延伸
//
//图的闭包：
//设图G=<V,E>为简单图，将图G中度数之和至少为|V|(节点数量)的非邻接节点连接起来
//重复这样的操作直到不再有这样的节点，所得到的的图为图G的闭包

//求汉密尔顿图是一个NP完全问题

//void hamilton_loop(graph_matrix g, edge_list e)
